In a reduced-redundancy computer storage system, each BLOB (Binary Large OBject—a finite sequence of zero or more bytes (or bits)) is represented as a sequence of subblocks from a pool of subblocks. FIG. 1 (prior art) shows a pool of subblocks and two BLOBs that are represented as lists of subblocks from the pool.
Each BLOB of data to be stored is divided into subblocks and matched against the subblocks in the pool. Each subblock in the new BLOB that is already present in the pool is replaced by a reference to the subblock in the pool. Each subblock in the new BLOB that is not in the pool is added to the pool. By storing only new unique subblocks, the storage system forms a reduced-redundancy representation of the BLOBs stored, and thereby reduces the amount of storage space used. FIG. 2 depicts the addition of a new BLOB 20 consisting of the subblocks ABCXY into a pool that already contains subblocks A, B and C 22. The new BLOB 24 is represented as a list of subblocks consisting first of the existing subblocks A, B and C and then of two new subblocks X and Y that are added to the subblock pool as a result of adding the new BLOB.
To implement this method, a reduced-redundancy storage system typically consists of the following components: a BLOB table 30 (to represent the BLOBs and allow them to be retrieved), a subblock pool 32 (to hold the actual subblock content), and a subblock index 34 (to quickly identify whether a subblock is present in the store and locate it if it is) (FIG. 3). Each of these components can be implemented in a wide variety of ways.
Of critical importance to the speed of a reduced-redundancy storage system is the subblock index. Whereas the BLOB table is typically accessed just once or twice for each BLOB stored, and the subblock pool can operate on subblocks in groups for greater efficiency, the subblock index is accessed (at least in a simplistic implementation) for every subblock that is presented to the system for storage. If the subblocks are a kilobyte each, this is about twenty thousand index lookups just to store twenty megabytes of data. It is therefore vital that the subblock index is fast.
The actual speed of access to the index depends on whether the index is held in memory or on disk, as a random memory access takes of the order of fifty nanoseconds whereas a random disk access takes of the order of ten milliseconds (about 200,000 times longer). The index could be held completely on disk, partially on disk, or entirely in memory. While it is clearly desirable for the index to reside entirely in memory, this may be impractical or too expensive if the index is large.
If some part of the index is to be held on disk, then it is important to design the index so as to minimize disk accesses, and in particular random access disk accesses.
Another requirement of an index data structure is that it be capable of scaling, and of scaling smoothly, as storage systems often grow to sizes that are larger than expected.
Aspects of the present invention provide a data structure that can grow smoothly while providing high speed access with a low number of random access disk operations.